package one;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
 * <p>
 * Each number in C may only be used once in the combination.
 * <p>
 * Note:
 * <p>
 * All numbers (including target) will be positive integers.
 * Elements in a combination (a1, a2, ... , ak) must be in non-descending order. (ie, a1 ? a2 ? ... ? ak).
 * The solution set must not contain duplicate combinations.
 * For example, given candidate set 10,1,2,7,6,1,5 and target 8,
 * A solution set is:
 * [1, 7]
 * [1, 2, 5]
 * [2, 6]
 * [1, 1, 6]
 */

public class Day09_Combination_Sum_II {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] sum, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (sum.length == 0) {
            return res;
        }
        Arrays.sort(sum);
        ArrayList<Integer> adds = new ArrayList<Integer>();
        dfs(sum, 0, target, adds, res);
        return res;
    }

    private void dfs(int[] num, int index, int target, ArrayList<Integer> adds, ArrayList<ArrayList<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<Integer>(adds));
            return;
        }
        HashSet<Integer> checks = new HashSet<Integer>();
        for (int i = index; i < num.length; i++) {
            if (target >= num[i] && !checks.contains(num[i])) {
                checks.add(num[i]);
                adds.add(num[i]);
                dfs(num, i + 1, target - num[i], adds, res);
                adds.remove(adds.size() - 1);
            }
        }
    }

}
